package letcode.problem.dynamicProgra;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 最长递增子序列的个数
 * https://leetcode.cn/problems/number-of-longest-increasing-subsequence/?envType=study-plan-v2&envId=dynamic-programming
 * */
public class NumberOfLongestIncreasingSubsequence {

    public static int findNumberOfLIS(int[] nums) {
        int m = nums.length;
        int[] dp = new int[m];
        int maxans = 1;
        int[] cnt = new int[m];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            dp[i] = 1;
            cnt[i]=1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {

                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (dp[j] + 1 == dp[i]) {

                        cnt[i] += cnt[j];
                    }
                }
            }
            if (dp[i] > maxans) {
                maxans = dp[i];
                ans = cnt[i];
            } else if (dp[i] == maxans) {
                ans += cnt[i];
            }

        }
        return ans;

    }

    public static void main(String[] args) {
        System.out.println(
                findNumberOfLIS(new int[]{
                        1,3,5,4,7
                })
        );
    }

}
